﻿// 0917train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）
机器人每次只能向下或者向右移动一步
机器人试图达到网格的右下角（在下图中标记为 “Finish” ）
问总共有多少条不同的路径

输入：m = 3, n = 7
输出：28
 */
int uniquePaths(int m, int n)
{
    //行m 列n
    vector<vector<int>>dynamic_vec(m, vector<int>(n));

    //第0个格有1种走法
    dynamic_vec[0][0] = 1;

    //第一列的走法（只能向右向下）
    for (int r=1;r<m; r++)
    {
        dynamic_vec[r][0] = 1;
    }

    //第一行的走法
    for (int c=1; c<n; c++)
    {
        dynamic_vec[0][c] = 1;
    }

    //行m 列n
    //dp[r][c]=dp[r-1][c]+dp[r][c-1]
    for (int r=1; r<m; r++)
    {
        for (int c=1; c<n; c++)
        {
            dynamic_vec[r][c] = dynamic_vec[r - 1][c] + dynamic_vec[r][c - 1];
        }
    }

    return dynamic_vec[m - 1][n - 1];

    //uniquePaths
}


/*
给定一个 m x n 的整数数组 grid
一个机器人初始位于 左上角（即 grid[0][0]）
机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）
机器人每次只能向下或者向右移动一步

网格中的障碍物和空位置分别用 1 和 0 来表示
机器人的移动路径中不能包含 任何 有障碍物的方格

返回机器人能够到达右下角的不同路径数量
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
 */
int uniquePathsWithObstacles(vector<vector<int>>&obstacleGrid)
{
    int row_size = obstacleGrid.size();
    int col_size = obstacleGrid[0].size();

    if (obstacleGrid[0][0] == 1)return 0;

    vector<vector<int>>dynamic_vec(row_size, vector<int>(col_size));

    //起点，路径数为1
    dynamic_vec[0][0] = 1;

    //第一列，没有障碍路径数为1
    for (int r=1; r<row_size; r++)
    {
        //障碍物1
        if (obstacleGrid[r][0] == 1)break;
        dynamic_vec[r][0] = 1;
    }

    //第一行，没有障碍路径数为1
    for (int c=1; c<col_size; c++)
    {
        if (obstacleGrid[0][c] == 1)break;
        dynamic_vec[0][c] = 1;
    }

    for (int r=1; r<row_size; r++)
    {
        for (int c=1; c<col_size; c++)
        {
            if (obstacleGrid[r][c] == 1) continue;
            dynamic_vec[r][c] = dynamic_vec[r - 1][c] + dynamic_vec[r][c - 1];
        }
    }

    return dynamic_vec[row_size - 1][col_size - 1];
	//uniquePathsWithObstacles
}


/*
 给定一个包含非负整数的 m x n 网格 grid ，
 请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小
说明：每次只能向下或者向右移动一步

输入
grid = [[1,3,1],[1,5,1],[4,2,1]]
输出
7
 */
int minPathSum(vector<vector<int>>& grid) {

    int row_size = grid.size(), col_size = grid[0].size();

    vector<vector<int>>dynamic_vec(row_size, vector<int>(col_size));

    //起点的和等于它本身
    dynamic_vec[0][0] = grid[0][0];

    //第一列
    for (int r=1; r<row_size; r++)
    {
        dynamic_vec[r][0] = dynamic_vec[r - 1][0] + grid[r][0];
    }

    //第一行
    for (int c=1; c<col_size; c++)
    {
        dynamic_vec[0][c] = dynamic_vec[0][c - 1] + grid[0][c];
    }

    for (int r=1; r<row_size; r++)
    {
        for (int c=1; c<col_size; c++)
        {
            int min_prev = min(dynamic_vec[r - 1][c], dynamic_vec[r][c - 1]);
            dynamic_vec[r][c] = min_prev + grid[r][c];
        }
    }

    return dynamic_vec[row_size - 1][col_size - 1];
    //minPathSum
}



/*
 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度
 输入
 nums = [10,9,2,5,3,7,101,18]
 输出
 4
 */

int lengthOfLIS(vector<int>& nums) {

    int v_size = nums.size();
    //递增最长子序列，最小为1，包含本身
    vector<int>dynamic_vec(v_size,1);

    for (int i=1; i<v_size; i++)
    {
        for (int prev=0; prev<i; prev++)
        {
            //如果前面有小于curr的数，dp[i]=dp[prev]+1
            if (nums[prev]<nums[i])
            {
                int dp_prev = dynamic_vec[prev];
                dynamic_vec[i] = max(dp_prev + 1, dynamic_vec[i]);

            }
        }

	    //for
    }

    int res = 1;
    for (auto&length:dynamic_vec)
    {
        res = max(res, length);
    }
    return res;
    //lengthOfLIS
}


/*
 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度
 如果不存在 公共子序列 ，返回 0 

一个字符串的 子序列 是指这样一个新的字符串：
它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列

示例 1
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 
 */
int longestCommonSubsequence(string text1, string text2) {

    int col_length = text1.size(), row_length = text2.size();
    int row_size = row_length +1, col_size = col_length +1;

    vector<vector<int>>dynamic_vec(row_size, vector<int>(col_size));

    //dp[0][0]=0 前0个字符公共0
    //dp[r][0]=0 text1前0个字符公共0
    //dp[0][c]=0 text2前0个字符公共0
    for (int r=1; r<row_size; r++)
    {
        for (int c=1; c<col_size;c++)
        {
            //如果r c不相等
            //3种情况,r在c不在，r不在c在，r不在c不在（无需考虑，长度小于前2种情况）
            if (text1[c-1]!=text2[r-1])
            {
                int prev_1 = dynamic_vec[r - 1][c];
                int prev_2 = dynamic_vec[r][c - 1];
                dynamic_vec[r][c] = max(prev_1, prev_2);
            }
            else
            {
                //如果r,c相等
                int prev = dynamic_vec[r - 1][c - 1];
                dynamic_vec[r][c] = prev + 1;
            }

        }
    }

    return dynamic_vec[row_size - 1][col_size - 1];
    //longestCommonSubsequence
}


/*
返回 两个数组中 公共的 、长度最长的子数组的长度

示例 1
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1]

示例 2
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5
 */
int findLength(vector<int>& nums1, vector<int>& nums2) {

    int col_length = nums1.size(), row_length = nums2.size();
    int row_size = row_length+1 , col_size = col_length+1 ;

    //初始化dp
    vector<vector<int>>dynamic_vec(row_size, vector<int>(col_size));

    //0位置，表示该数组没有元素
    //dp[0][0]=0; dp[0][c]=0; dp[r][0]=0;

	//相等，长度等于前序+1
    int result = 0;
    for (int r=1; r<row_size; r++)
    {
        for (int c=1; c<col_size; c++)
        {
            if (nums2[r-1]==nums1[c-1])
            {
                dynamic_vec[r][c] = dynamic_vec[r - 1][c - 1] + 1;
                result = max(dynamic_vec[r][c], result);
            }
        }
    }

    return result;
    //findLength
}

int main()
{
	{
        //nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
        vector<int>nums1 = { 1,2,3,2,1 }, nums2 = { 3,2,1,4,7 };

        cout << findLength(nums1, nums2);

        return 0;
	}
	{
        string text1 = "abc", text2 = "def";

        cout << longestCommonSubsequence(text1, text2);
        return 0;
	}
	{
        vector<int>nums = { 10,9,2,5,3,7,101,18 };
        cout << lengthOfLIS(nums);

        return 0;
	}
	{
        //grid = [[1,3,1],[1,5,1],[4,2,1]]
        vector<vector<int>>grid = { {1,3,1},{1,5,1},{4,2,1} };

        cout << minPathSum(grid);
        return 0;
	}
	{
        vector<vector<int>>obstacleGrid = { {0,0,0},{0,1,0},{0,0,0} };

        cout << uniquePathsWithObstacles(obstacleGrid);

        return 0;
	}
    int m = 3, n = 7; //28
    cout << uniquePaths(m, n);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
